1. Field of the Invention
The present invention relates to a method for efficiently revoking digital identities such as certificates generated by a public-key cryptography system.
2. Discussion of Related Art
Digital Identities
Digital identities (and author-identities of messages) which identify a particular person or entity are important for business, private, and government use of the Internet. For example, digital identities are needed for on-line shopping, business-to-business transactions, on-line banking, code-authentication, company-internal identities, and other network and world wide web related transactions. The U.S. Federal government, NIST, the U.S. Post Office, Visa and Master Card, some major banks, and private companies (like VeriSign, SIAC, IBM, GTE, and Microsoft) are all building digital identity infrastructures. Although the general design of all these schemes is similar, and typically relies on public-key cryptography and Certificate Authority services (both of which are described below), the details (and hence the efficiency) of what it means for a digital identity to be valid, and how it can be revoked differs from scheme to scheme.
Public Key Cryptography
It is often desirable to encrypt a message, such as a digital message, so that only certain authorized persons may access the message. All others are unable to access the message. One way this may be done is by taking the message, called a plain text message, and encrypting it into a cipher text message. The cipher text message appears as gibberish. The cipher text message may be decrypted back into the plain text message only by those having the corresponding private key (described below). Public key cryptography is a well known way to encrypt messages in this way.
Public key cryptography may also be used to provide a xe2x80x9cdigital signaturexe2x80x9d to a message. The digital signature is an author identity which verifies that the message originated from the party signing the document. This may be done by a party using its private key to sign a message. The signature may be verified by anyone having the party""s public key, but may only be signed by the party having the private key (public and private keys are described below).
In a typical public key cryptography system (also referred to herein as a xe2x80x9cpublic key cryptosystemxe2x80x9d), each user u has a public key (or exponent) PKu and a secret key (or exponent) SKu. For a particular party i, party i""s public key PKi is known to everyone, but the secret key SKi is known only to party i. A plain text message m to user i is encrypted to form the cipher text message x using a public operation P which makes use of the public key PKi known to everyone, i.e., x=P(m,PKi). The cipher text message x is decrypted using a decryption operation D which makes use of the secret key SKi, i.e., m=D(x,SKi). Anyone given the public key can encrypt a message using the public operation. Only party i who has the secret key SKi can perform the secret operation to decrypt efficiently the encrypted message x to obtain clear text message m.
A digital signature may be added to a message m to identify that the party xe2x80x9csigningxe2x80x9d the message is user i, the party identified as the message originator, and not an imposter. A digital signature may be associated with a message m by applying a signing algorithm S on the message m using the signing party""s secret key SKi i.e., =S(m, SKi). Anyone given that party""s public key PKi may verify the authenticity of the signature by applying a verification algorithm V on the signature using the signing party""s public key PKi, i.e. V(PKi, m,) {valid or not valid}.
FIG. 1 is a block diagram of a typical cryptography device 100, such as may be used in a public key cryptosystem. The device 100 has a processor 102 including one or more CPUs 102, a main memory 104, a disk memory 106, an input/output device 108, and a network interface 110. The devices 102-110 are connected to a bus 120 which transfers data, i.e., instructions and information between each of these devices 102-110. The processor 102 may use instructions in the memories 104, 106 to perform functions on data, which data may be found in the memories 104, 106 and/or received via the I/O 108 or the network interface 110.
For example, a plain text message (or unsigned message) may be input via the I/O 108 or received via the network interface 110. The plain text message (or unsigned message) may then be encrypted (or digitally signed) using the processor 102 and perhaps software stored in the main memory 104 or the disk memory 106. The encrypted message (or digitally signed message) may be transmitted to another party via the network interface 110 connected to a local area network (LAN) or wide area network (WAN). Similarly, a cipher text message (or digitally signed message) may be received via the network interface 110 and decrypted using the processor 102 and perhaps software stored in the main memory 104 or the disk memory 106. The decrypted message, now in plain text, or signature verification may be, for example, viewed on a monitor.
FIG. 2 illustrates a network 200 over which cryptography devices 100 may communicate. Two or more cryptography devices 100, 100, 100 may be connected to a communications network 202, such as a wide area network which may be the Internet, a telephone network, or leased lines; or a local area network, such as an Ethernet network or a token ring network. Each cryptography device 100 may include a modem, network interface card, or other network communication device 204 to send encrypted or digitally signed messages over the communications network 202. A cryptography device 100 may be a gateway to a sub-network 206. That is, the device 100 may be an interface between a wide area network 202 and a local area (sub) network 206.
As discussed in more detail below, in a public key cryptosystem, two communicating parties, such as cryptography devices 100 and 100 may communicate with a third party, such as cryptography device 100, to certify that each party is not an imposter. This third party is often called a certification authority.
One problem with public key cryptography is that for one party, say party A, to communicate with another party, say party B, A needs to obtain party B""s public key PKB. A may do this in a number of ways, for example, A""s cryptography device may obtain PKB (1) directly from B""s cryptography device, (2) from A""s cryptography device""s own database (if, for example, A and B have previously communicated), such as disk memory 106, or (3) from a trusted third party such as a certification authority. A security problem arises if B""s digital identity is stolen or canceled before it expires.
Certification Authorities
In some public-key cryptosystems, this security problem is avoided by having public keys certified by a trusted third party. This trusted party is often referred to as a certification Authority (CA). A CA issues a public key certificate (PKC), which contains a party""s public key, information about the party, such as its name, address, account or serial number, certificate expiration date, the CA""s identity, and the CA""s digital signature certifying that the public key belongs to the party presenting the certificate. Thus, if A wishes to communicate with B, B sends A its public key PKB and its public key certificate. A checks the authenticity of PKB and the public key certificate by checking them against the public keys for B and CA.
Digital identities, such as PKCs, are not unlike credit cards (and indeed may represent a credit card account) in that they typically have an expiration date. Moreover, a digital identity, just like a credit card, may be revoked due to a change in the party""s status, a security breach, or other reason. Without a method for certificate revocation, these digital identities may be used by unauthorized parties. Just as with credit cards, occasional revocation is a fact of life. According to some estimates, about 10% of digital identities will usually be revoked before they expire. Thus, an important element of any CA scheme (or hierarchy) is its revocation procedure.
The CA may keep a list of invalid but not yet expired certificates. Thus, when A receives PKB and its accompanying certificate, A should also check this list to make sure that the certificate is valid, that is, it is not expired or revoked. This typically involves a communication with the CA in each user-to-user transaction, which is an undesirable use of communications network 202 resources.
A digital identity revocation scheme may include one or several trusted certificate authorities which distribute at regular intervals (for example each day) information regarding revoked certificates to several untrusted directories. (The reason for having many directories is to allow replication of data.) For each day, any directory should be able to provide a proof whether any user""s u public key is valid or revoked. The directory may provide proof of the revoked status either to the user himself (who can then pass it along to any other user) or any other user who wishes to determine that user""s identity is still valid. The critical costs of the scheme are the size of the proof of the validity of user""s identity (i.e., this proof should be as small as possible, since this is the most frequently used operation) as well as the communication from the Certificate Authority to the directories for each period.
Prior Solutions to Certificate Revocation
Private-channel solution: Credit Cards
Consider the credit card system where a seller queries a central database to determine whether a customer""s credit card is valid and has an available credit limit. This is similar to determining the revocation status of a PKC. This credit card-type solution cannot be used for PKC revocation. This is because there are two fundamental assumptions that are made for the credit card infrastructure which are not necessarily true for a public key infrastructure: (1) a party verifying a credit card assumes it contacts the proper party when it calls the credit card company to verify a card; and (2) the verifying party assumes that the credit card company""s database is available on-line, i.e., 24 hours a day, seven days a week, and is relatively up-to-date. These assumptions may not necessarily be true for all public key infrastructures.
Direct Signing Scheme
In this scheme, a CA may regularly sign and send a fresh certificate for each unrevoked public key. User U presents the latest certificate of PKU when interacting with others. A recipient checks the certificate""s date and authenticity. If the certificate has the current date and otherwise is authentic, the certificate has not been revoked as of the last time the certificate was issued. This eliminates the step of verifying the revocation status of the PKC when it is presented. Because Periodically signing and sending all users"" certificates (as frequently as every night) is computationally prohibitive and a burden on the communication system. This solution is not used in practice.
Certificate Revocation List
Currently a certificate revocation list (CRL) protocol is used by some CAs. A CRL is a complete list of revoked certificates. The CA periodically (such as daily or bi-weekly) generates and signs a complete list, or a modification of a previous list, of revoked certificates. Whenever the CA is queried about the revocation status of a certificate, the CA presents the inquiring party with the latest CRL. (Alternatively, the CRLs may be sent to the untrusted directories.) The inquiring party may store the CRL for the rest of the day (or other time period) to check the revocation status of public keys of other users if the public key does not appear on the CRL, it is probably valid. There are many variations of the CRL scheme. Because in a typical public key cryptosystem, the number of revoked certificates may be on the order of several hundred thousand, a CRL may be very long. As a result, this scheme has exorbitantly high communications costs.
Micali Scheme
In an improvement on the CRL scheme, one inventor, Micali, uses an off-line/on-line signature scheme called CRS, which is an acronym for xe2x80x9ccertification revocation scheme.xe2x80x9d This CRS is designed to reduce CA-to-users communications costs. In Micali""s scheme, each certificate has an accompanying secondary token for that certificate which is updated periodically, such as daily. This secondary token is unique to that certificate and is shorter than a typical certificate. During transactions, these short tokens are used as proofs of non-revocation instead of long certificates.
In the Micali scheme, for each user, the CA""s cryptography device generates a random number. The cryptography device then uses this random number to generate a chain of tokens unique to that user""s certificate. This chain may be generated by repeatedly performing a one-way function, such as a one way hash function, on the random number. (Briefly, a one-way function is a function that is easy to compute but hard to invert on an overwhelming fraction of its range. In a good one-way hash function, given a hash function output value, it is computationally infeasible to determine the input string hashed to that value.)
For a certificate that is valid for D days (or other time period), the random number is hashed D times (say, for example, 365 times for a certificate valid for one year). The 365th hash value is called the zero token. The zero token is included on the certificate signed using the CA""s public key. To verify the signer on the ith day (say day 200) the CA sends the D-ith token (i.e., the 165th token). The recipient uses his cryptography device to perform the hash function on the D-ith token i times (i.e., 200 times). If the result is the same as the zero token and the zero token has been signed according to CA""s public key, the certificate is verified. Given any ith token, it is easy to determine if that token is in the chain of tokens for that certificate by hashing it a certain number of times. The result is compared to the zero token. Given the zero token and all tokens up to and including the ixe2x88x921 token, however, it is computationally infeasible to determine the ith token (where i less than D).
Because these secondary signatures are short (about 100 bits long) and easy to compute, the Micali CRS scheme is preferred over the direct signing scheme and the CRL scheme. One disadvantage is that the scheme requires (for each day) the CA to send N-R tokens to each directory where N is the number of public keys and R is the number of revoked keys. Thus, there is a high communications cost.
Micali also considers the case where a directory may act maliciously by not forwarding the day i-token of a user it received from the CA to the user or verifier. A non-revoked user could thus be considered revoked by a verifier. To prevent this, Micali modifies his scheme as follows. For each user the CA also chooses a random xxe2x80x2u, the xe2x80x9crevocation token,xe2x80x9d and includes f(xxe2x80x2u) in u""s certificate, along with the zero token and other certificate information. When u""s public key is revoked, the CA sends the revocation token to the directories. When a directory is queried about a user on day i+1 it returns either the day i token or the revocation token for that user.
In this scheme, the total daily update cost is O(N), meaning on the order of N, where N is the number of certificates. That is, the status of each certificate is updated daily. Therefore, this scheme has a high update cost, even when there are very few current revocations. The expected total daily queries cost is O(Q), meaning on the order of the number of queries. This is because a 100-bit secondary token is provided for each one of the queries. In a typical public key cryptosystem, the values for N and Q are in the several millions. This scheme is xe2x80x9cexpensivexe2x80x9d to implement because it requires a great number of secondary tokens for updating.
Recently, Naor-Nissim have improved upon a scheme by P. Kocher. For the details of the scheme see M. Naor and K. Nissim, xe2x80x9cCertificate Revocation and Certificate Update,xe2x80x9d Proceedings of USENIX"" 98, the contents of which are incorporated herein by reference. For R revoked keys, in the Naor-Nissim scheme the CA maintains an authenticated 2-3 tree of hash values of depth O (log R). For each public key which is revoked in an update period, the CA updates this special tree by computing O (log R) new hash values. As long as one key is added to this revocation tree the root is recomputed and signed. The CA sends to the directories the lists of users to insert and delete, and a signature of the root. The directories insert and delete the users from the tree, recompute the hash values, and check the signature of the root. When a user queries a directory concerning the revocation status of a key, the directory sends O (log R) hash values and the signature of the root. To verify the revocation status of a key, a user must compute O(log R) hash values, compare them in a specified way with the hash values from the directory and verify the signature of the root hash value. While the CA to directory communication of this scheme is small, in some situations the verification of the revocation status of the user is more expensive than the Micali scheme described above.
It is an object of the present invention to provide a digital identity or public key revocation scheme that is less expensive, in terms of overall computing and communications network resources, than the prior art schemes.
These and other objects of the present invention are provided by a method according to the present invention. A digital identity revocation scheme includes a plurality of digital identities. This plurality of digital identities is grouped into sets, at least some of these sets including a plurality of digital identities. These sets are associated with revocation checking information. Each of the plurality of the digital identities is associated with revocation checking information for each set to which that digital identity belongs. At least some sets not containing a revoked identity are identified. Revocation status information is generated for the identified sets. Whether or not a particular digital identity is revoked is determined by comparing the revocation status information and the revocation checking information associated with the digital identity.
In a preferred embodiment of the present invention, a list of tokens is part of each digital identity or certificate maintained by the CA""s device, such as a cryptography device. Each digital identity or certificate may be grouped into sets with other digital identities"" certificates. Each such set is associated with revocation checking information, such as a token. Every digital identity in the set contains the revocation checking information (i.e., token) for that set in its certificate. Revocation status information for the sets may be generated by updating certain of these tokens periodically to indicate valid (unrevoked and unexpired) certificates, the number of updated records is reduced. Moreover, in response to a status query, a single token may be transmitted in response. To verify that a presented identity or certificate is authentic, a one-way function may be performed several times on the received token. In another embodiment, information in addition to the token may be transmitted. If the results of the function match one of the tokens in the certificate, the identity is verified. This results in a more efficient overall use of both computing and communications network resources.
In a first preferred embodiment, the data revocation structure is a binary tree. Each leaf of the binary tree represents a user in the cryptosystem. Each leaf has associated with it a path of nodes from the leaf to the root of the tree. These nodes are shared with one or more other leaves. Each node in the path has a unique value associated with it called the token value. This unique token value is processed at least D times using a one-way function, such as a one-way hash function, where D is the time period that a certificate is valid. This processed value is called the zero token value for that node. The (at least) D intermediate values between the token value and the zero token value comprise a chain of token values associated with that node. For purposes of this application, an i token is the output value of the one way hash function applied to the token value D-i times. Note that given the zero token value, its is computationally infeasible to determine any of the D previous values. Given one of the D previous values, however, it is easy to determine the zero token value by performing the one-way function on the value a certain number of times.
The certificate of the user represented by the leaf includes the zero token value for each node in its path from leaf to root. The tree is periodically updated to indicate valid and revoked certificates. This update operation includes a selection process, in which certain nodes are selected for updating, and a token update process, in which the selected nodes are updated. In the selection process, the fewest number of nodes on the binary tree satisfying the following two properties are selected for updating:
1. At least one selected node is on the path from each non-revoked and not-yet expired certificate leaf to the root of the tree; and
2. None of the selected nodes is on the path from any revoked user-certificate to the root of the tree.
The token update process updates the selected nodes. Assume it is day i of the system. The ith value of a node""s chain is selected. This update may be done, for example, by performing the one-way function on the node""s token value a certain number of times, or by selecting a pre-computed value stored in a memory.
A certificate may be verified in the following manner. A token is valid on day i+1 if it has been updated on day i. If on day i+1, a first party A wishes to verify a second party B""s digital identity (public key certificate), party A obtains a token for party B either from the CA (or other repository, such as a directory or directories) or from party B who obtained the token from the CA. If the digital identity is revoked or expired there is no token available from the revocation structure or, additionally, a revocation token may be sent indicating that the digital identity is no longer valid. If the digital identity is not revoked, the CA sends an updated token. Because (1) each valid certificate has a least one valid token in its chain due to the first selection property described above and (2) each revoked or expired certificate has no valid tokens in its chain due to the second selection property described above, if the certificate has at least one valid token in its chain, it is a valid certificate. The CA sends to A one of the valid tokens. Thus, A has verified that B""s digital identity has not been revoked or expired.
A has not yet determined that the certificate it is verifying is authentic, i.e., not a fake or forgery. A""s cryptography device receives a token, which is the unique token value of the selected node hashed a certain number of times (i.e., D-i times) to the D-ith value. A""s cryptography device performs the one-way function on this received token a certain number of times to obtain the zero token value. Recall that B""s certificate includes the zero token value of each node in the path from the node representing the user (the leaf) to the root of the tree. If the value determined by A""s crytography device matches one of the zero token values on the certificate A is verifying, then the certificate is verified as belonging to party B.
In a second preferred embodiment, a more general formulation is used to generate the data revocation structure. The universe of users"" certificates comprises a number of singleton sets, each containing a digital identity corresponding to a user certificate. These singleton sets are grouped into c disjoint sets (where c is an integer). These c sets are arranged into larger sets. For each of the c sets and larger sets, there is a chain. Each user""s certificate includes the zero token value for each chain of each set to which the user belongs. Similar updating and verification processes are performed using this data revocation structure.
In a third embodiment, the updating process is performed incrementally, where the revocation of time period i revokes only those certificates revoked during that time period. As a result, when the data revocation structure is updated, it will consider only those digital identities revoked since the last update, resulting in a more efficient update process. Instead of having the CA provide a single valid token to verify the certificate, on time period i+1, the user presents proof that its certificate was valid for a period from time period 1 through time period i. No valid token exists on the time period that the user""s certificate was revoked. Because there is no valid token for that time period, the revoked user (revoked on or before time period i) cannot present a valid token for each time period from time period 1 through time period i.
The present invention is an improvement over the prior art methods. As described below, the invention provides a significant reduction in the overall use of computation and communications network resources.